import java.util.ArrayList;
import java.util.List;

public class Main {

    /**
     * 全排列
     */
    List<List<Integer>> ret;
    boolean[] check;
    List<Integer> path;
    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        check = new boolean[nums.length];
        path = new ArrayList();
        dfs(nums);
        return ret;
    }
    public void dfs(int[] nums) {

        if(path.size() == nums.length) {
            ret.add(new ArrayList(path));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(check[i] == false) {
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }


    /**
     * 子集解法1
     */
    /*List<Integer> path;
    List<List<Integer>> ret;

    public List<List<Integer>> subsets(int[] nums) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        dfs(nums, 0);
        return ret;
    }

    void dfs(int[] nums, int i) {
        if(i == nums.length) {
            ret.add(new ArrayList<>(path) );
            return;
        }
        //选写前面
        path.add(nums[i]);
        dfs(nums, i + 1);
        path.remove(path.size() - 1);
        //不选写后面
        dfs(nums, i + 1);
    }*/
    /**
     * 解法2
     */
   /* List<Integer> path;
    List<List<Integer>> ret;

    public List<List<Integer>> subsets(int[] nums) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        dfs(nums, 0);
        return ret;
    }

    void dfs(int[] nums, int i) {
        ret.add(new ArrayList<>(path));
        for(int pos = i; pos < nums.length; pos++ ) {
            path.add(nums[pos]);
            //剪枝
            dfs(nums, pos + 1);
            //恢复线程
            path.remove(path.size() - 1);
        }
    }*/


    /**
     * 找出所有子集的异或总和在求和
     */
    /*int sum;
    int path;

    public int subsetXORSum(int[] nums) {
        sum = 0;1
        path = 0;
        dfs(nums, 0);
        return sum;
    }
    void dfs(int[] nums, int pos) {
        sum += path;
        for(int i = pos; i < nums.length; i++) {
            path ^= nums[i];
            dfs(nums, i+1);
            //恢复现场
            path ^= nums[i];
        }
    }*/

    /*List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums);
        return ret;
    }
    void dfs(int[] nums) {
        if(path.size() == nums.length) {
            //已经到底了
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(check[i] == false && ( i == 0 || nums[i] != nums[i - 1]  || check[i - 1] == true)) {
                //递归
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path.remove(path.size() - 1);
            }

        }
    }
*/
    /*List<String> ret;
    StringBuffer path;
    String[] hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        if(digits.length() == 0) {
            return ret;
        }
        path = new StringBuffer();

        dfs(digits, 0);
        return ret;
    }
    void dfs(String digits, int pos) {
        if(pos == digits.length()) {
            ret.add(path.toString());
            return;
        }
        String cur = hash[digits.charAt(pos) - '0'];
        //遍历cur内的每个字符进行递归
        for(int i = 0; i < cur.length(); i++) {
            path.append(cur.charAt(i));
            dfs(digits, pos + 1);
            //恢复现场
            path.deleteCharAt(path.length() - 1);
        }
    }*/




}
